package com.markus.code.exam.pingduoduo;

import java.util.Scanner;

/**
 * Author:markusZhang
 * Date:Create in 2020/9/1 20:44
 * todo:
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
            int m = scanner.nextInt();
            int n = scanner.nextInt();
            int []c = new int[m];
            int []v = new int[m];
            for (int i=0;i<m;i++){
                c[i] = scanner.nextInt();
                v[i] = scanner.nextInt();
            }
            Main demo = new Main();
            System.out.println(demo.process(v,n,0,0));
        }
    }
    private int process(int []values,int weight,int index,int sum){
        if (weight <= 0){
            return Integer.MIN_VALUE;
        }
        if (index == values.length){
            return sum;
        }
        int yes = process(values, weight - values[index], index + 1, sum + values[index]);
        int no = process(values,weight,index+1,sum);
        return Math.max(yes,no);
    }
}
